OSPF is a widely used protocol for routing within an autonomous system domain. OSPF implements a two-level hierarchical routing scheme through the deployment of OSPF areas. Each OSPF area consists of a collection of subnets interconnected by routers. Information about links and subnets within an area is flooded throughout the area. As a result, every router connected to an area knows the exact topology of the area—this includes the subnets and the links connecting routers in the area. However, details of an area's topology are not advertized beyond the area's borders and are thus hidden from other areas. Instead, subnet addresses within each area are aggregated and only aggregates are flooded into the rest of the network (thus, making an area's subnets reachable from the remainder of the network). This task of advertizing aggregate information about subnets in an area is carried out by area border routers (ABRs), that is, routers attached to two or more areas.
OSPF areas and address aggregation enable OSPF to scale when networks contain hundreds or thousands of subnets. Specifically, they help to optimize router and network resource consumption, as follows:
1. Router memory. Routing tables only need to contain entries corresponding to aggregate addresses for areas not connected to the router. Only for areas directly connected to the router, are individual subnet addresses in the area stored in its routing table. This leads to smaller routing table sizes and thus lower memory requirements at routers.
2. Router processing cycles. The link-state database is much smaller since it only includes summary information for subnets belonging to areas that are not directly connected to the router. Consequently, the cost of the shortest-path calculation decreases substantially.
3. Network bandwidth. For subnets within each area, only aggregate address information (and not individual subnet addresses) is flooded into the rest of the network. As a result, the volume of OSPF flooding traffic necessary to synchronize the link-state databases is significantly reduced.
However, despite the above-mentioned benefits of address aggregation, trade-offs are involved. This is because address aggregation necessarily results in loss of information, which, in turn, can lead to suboptimal routing. In order to see this, one must examine in more depth how routing works in the presence of aggregation.
During routing, each ABR attaches a weight to each aggregate advertized by it. This weight is foundational for determining the path used by a router external to the area to reach subnets covered by the aggregate. From among all the ABRs advertizing the aggregate (with possibly different weights), the external router chooses the one (say b) for which the sum of the following two is minimum: (1) the length of the shortest path from the external router to the border router b, and (2) the weight advertized by b for the aggregate. IP packets from the external router to every subnet covered by the aggregate are thus forwarded along the shortest path from the external router to b and subsequently along the shortest path from b to the subnet. However, for a certain subnet, this path may be suboptimal since there may be a shorter path from the external router to the subnet through an ABR different from b. The following example, made with reference to FIG. 1, illustrates this problem.
FIG. 1 illustrates an exemplary autonomous network, generally designated 100. The network 100 is illustrated as having areas 0.0.0.0, 0.0.0.1, 0.0.0.2 and 0.0.0.3. The network 100 includes various routers 111, 112, 113, 114, 115, 116, 117, 118, 119 interconnecting subnets 121, 122, 123, 124, 125, 126, 127, 128. FIG. 1 also illustrates various subnet addresses and weights of each link connecting a pair of routers (e.g., routers 113, 115). The ABR b1 113 belongs to the area 0.0.0.1, the ABR b2 114 to te area 0.0.0.2, and the ABRs b3 115 and b4 116 to the area 0.0.0.3. Subnet addresses in the area 0.0.0.3 can be aggregated to different degrees. For instance, the aggregate 10.1.0.0/21 covers all the subnets in the area 0.0.0.3. In contrast, 10.1.4.0/22 covers only subnets 10.1.4.0/24, 10.1.5.0/24, 10.1.6.0/24 and 10.1.7.0/24, while 10.1.2.0/23 covers only subnets 10.1.2.0/24 and 10.1.3.0/24.
Suppose one of the aggregate addresses advertised by the ABRs of the area 0.0.0.3 is 10.1.4.0/22. Suppose further that each ABR assigns a weight to the aggregate which is essentially the distance of the furthest component in the aggregate from the router. Thus, router b3 115 advertizes 10.1.4.0/22 with a weight of 1100 (the distance of the subnet 10.1.6.0/24 from ABR b3 115), while the router b4 116 advertizes 10.1.4.0/22 with a weight of 1250 (the distance of the subnet 10.1.4.0/24 from the ABR b4 116). Thus, the ABR b1 114 belonging to the area 0.0.0.1 forwards all packets to the subnets in 10.1.4.0/22 through the ABR b3 115, since the shortest path to the aggregate through the ABR b3 115 has a length of 100+1100=1200, while the shortest path through the ABR b4 116 has length 200+1250=1450. Note, however, that the path from the ABR b1 114 to the subnets 10.1.6.0/24 and 10.1.7.0/24 passing through the ABR b3 115 has a length 1200 and is suboptimal. The shortest path from the ABR b1 114 to the subnets is through the ABR b4 116 whose length is only 400.
Further, note that considering different weight assignments for the aggregates does not alleviate the problem. The root of the problem is that a single ABR is selected by the ABR b1 114 for reaching all subnets in 10.1.4.0/22. If the ABR b4 116 is chosen instead of the ABR b3 115, then the paths from the ABR b1 114 to the subnets 10.1.4.0/24 and 10.1.5.0/24 through ABR b4 116 become much longer (whose length is 200+1250=1450) than the shortest paths to the subnets that pass through the ABR b3 115 (whose length is 100+50=150).
From the above example, it follows that address aggregation can potentially introduce an error in the optimal route calculation which is based on shortest paths. For instance, as illustrated in the example, when the aggregate address 10.1.4.0/22 is advertized with weights 1100 and 1250 by the ABRs b3 115 and b4 116, the router b1 111 selects the ABR b3 114 for the aggregate. This results in an error of 800 in the selected path from the ABR b1 114 to each of the subnets 10.1.6.0/24 and 10.1.7.0/24. The introduced error is essentially the difference between the length of the selected path (1200) and the length of the shortest path from the router b1 111 to each of the subnets (400). Note that the selected paths from the router b1 111 to the other two subnets 10.1.4.0/24 and 10.1.5.0/24 are the shortest paths, and so no error is introduced due to the subnets 10.1.4.0/24 and 10.1.5.0/24.
The primary reason for suboptimal paths being selected when subnets are aggregated is that a single weight is used by each ABR for all the subnets in the aggregate. A single weight may be incapable of accurately capturing the distance of the border router to every subnet covered by the aggregate. The problem is further exacerbated when the subnets are spread across the area with some subnets being closer to one border router while others being closer to a different border router. This was precisely the case in FIG. 1, where the aggregate 10.1.4.0/22 spans the subnets 10.1.5.0/24 (closer to the ABR b3 115) and 10.1.6.0/24 (closer to the ABR b4 116), the distance between whom is greater than 1000. As a result, a single weight advertized for aggregate 10.1.4.0/22 is not representative of the distance between a border router and subnets in 10.1.4.0/22.
Accordingly, what is needed in the art is a better way to select OSPF aggregates and their associated weights thereby to avoid suboptimization of routing in a network.